1. Field
This technology disclosed herein relates to the field of visualizing hierarchical data structures.
2. Background
There are many prior-art techniques for the visualization of hierarchical data structures (tree structures) that interconnect nodes. Examples of hierarchical data structures include file systems, organization charts, and taxonomies. In addition, many other richer graph structures, such as web sites, family trees, and social networks, are amenable to hierarchical data structure-based visualizations. Exponential increases in processing power, networking, and immense data storage have given rise to increasingly massive data sets and the need to visualize this information.
There is a problem with massive data sets being presented on limited display areas when the breadth or depth of a visualization of a hierarchical data structure exceeds the bounds of the display area. Common approaches to this problem use scrolling, panning, and/or scaling techniques. In addition, some techniques allow the visualization of the nodes to overlap (for example, most cone-tree embodiments).
A “Degree-Of-Interest” Tree (DOITree) can be represented as a hierarchical data structure where the nodes contain (or are associated with) an interest value (such as a degree-of-interest) and a payload. The layout of the DOITree structure and the payload depends on an interest value associated with each node in the tree. Some versions of DOITrees are interactive trees with animated transitions that fit within a bounded region of space and whose layout depends dynamically on the user's estimated degree-of-interest. DOITrees can use focus+context techniques to achieve the goals of logical filtering of nodes, using the estimated degree-of-interest to determine which nodes to display; geometric distortion, changing node sizes to match the estimated interest; semantic zooming of content based on node size; and aggregate representations of elided subtrees.
Similar in spirit to DOITrees is Plaisant et al.'s SpaceTree, which uses logical filtering and aggregation of nodes, combined with animation and automated camera management, to visualize tree structures. SpaceTree supports multiple foci, search, and filtering. However, for large hierarchical data structures SpaceTree usage often requires significant manual panning.
The visualization of massive data sets using exiting algorithms is computationally expensive. It would be advantageous to provide an improved, computationally efficient, visualization of hierarchical data structures that allows multiple foci and that can be presented within a constrained display area.